#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#include <assert.h>

typedef double (*func_t)(double);

// 返回funcs中所有函数的复合函数，即f(x) = fn(...f2(f1(x)))
double composite(func_t funcs[],int n,double input)
{
	double output = input;
	for (int i = 0; i < n; i++)
	{
		output = funcs[i](output);
	}
	return output;
	
}


void check1()
{
	double (*test1[3])(double) = {sin,cos,exp};
	assert(fabs(composite(test1,3,0.5) - 2.428467) < 1e-6);
	double (*test2[4])(double) = {log,sin,cos,exp};
	assert(fabs(composite(test2,4,1) - 2.718282) < 1e-6);
}

// 二叉树节点
struct Node{
	int val;	// 节点值
	struct Node *left;	// 左儿子
	struct Node *right; // 右儿子
};

// 使用malloc创建一个节点，并初始化节点
struct Node *newNode(int val)
{
	struct Node *node = (struct Node *)malloc(sizeof(struct Node));
	node->val = val;
	node->left = NULL;
	node->right = NULL;
	return node;
}

// 插入一个节点，如果val比当前节点值小，插入左子树，否则插入右子树
void insert(struct Node *root, int val)
{
	if (val < root->val)
	{
		if (root->left == NULL)
		{
			root->left = newNode(val);
		}
		else
		{
			insert(root->left, val);
		}
	}
	else
	{
		if (root->right == NULL)
		{
			root->right = newNode(val);
		}
		else
		{
			insert(root->right, val);
		}
	}
}

// 遍历二叉树，先遍历左儿子，然后遍历自己，最后遍历右儿子，将遍历结果存入数组中，返回数组长度
int traverse(struct Node *root, int *arr)
{
	static int i = 0;
	if (root->left != NULL)
	{
		traverse(root->left, arr);
	}
	arr[i++] = root->val;
	if (root->right != NULL)
	{
		traverse(root->right, arr);
	}
	return i;
}

// 释放二叉树的内存
void freeTree(struct Node *root)
{
	if (root->left != NULL)
	{
		freeTree(root->left);
	}
	if (root->right != NULL)
	{
		freeTree(root->right);
	}
	free(root);
}

void check2()
{
	struct Node *root = newNode(5);
	insert(root, 3);
	insert(root, 7);
	insert(root, 2);
	insert(root, 4);
	insert(root, 6);
	insert(root, 8);
	int arr[7];
	int len = traverse(root, arr);
	assert(len == 7);
	for (int i = 0; i < len; i++)
		assert(arr[i] == i + 2);
	freeTree(root);
}

int main()
{
	check1();
	check2();
	puts("Tests passed!");
	return 0;
}